#ifndef __BLOOM_FILTER_WM__
#define __BLOOM_FILTER_WM__

#include "thisinc.h"
#include "bitmap.h"

namespace xm
{
	namespace u32wm
	{
		struct skiptable_t
		{
			static inline uint16_t hashv( const uint8_t* binp )
			{
				return (*(le::U16*)(binp-1)); 
			}
			enum { FIXPTN_BYTES = sizeof(uint32_t), };
			enum { SUFFIX_BYTES = sizeof(uint16_t), };
			enum { TABLE_SIZE	= 0x10000 };

			uint8_t			_shift[TABLE_SIZE];

			inline skiptable_t()
			{
				clear();
			}

			inline VOID clear()
			{
				memset( _shift, FIXPTN_BYTES-SUFFIX_BYTES, TABLE_SIZE );
			}
			inline size_t addu32( const uint32_t* v32p )
			{
				const uint8_t * binp = (const uint8_t*)v32p;
				size_t sLast = FIXPTN_BYTES - 1;
				size_t sFirst = 1;
				for (size_t j = sLast; sFirst <= j; --j)
				{
					uint16_t hash = hashv(binp+j);
					size_t shift = sLast - j;
					if (shift < _shift[hash]) 
					{
						//printf( "%04X -> %d\n", hash, shift );
						_shift[hash] = (uint8_t)shift;
					}
				}
				return TRUE;
			}
			inline size_t get_shift( uint16_t _hash )
			{
				return _shift[_hash];
			}
			inline size_t get_shift( const uint32_t* v32p )
			{
				const uint8_t * pl = ((const uint8_t *)v32p) + FIXPTN_BYTES -1;
				return _shift[ hashv(pl) ];
			}
		};

		struct bloom32_t : public bit_map_t
		{
			inline void addu32( uint32_t * v32p )
			{
				uint32_t v32 = *v32p;
				setbit( hash_001(v32) );
				setbit( hash_002(v32) );
				setbit( hash_003(v32) );
				setbit( hash_004(v32) );
			}
			inline size_t maybe_hit( uint32_t * v32p )
			{
				uint32_t v32 = *v32p;
				if( !testbit( hash_002(v32)) ) return FALSE;
				if( !testbit( hash_003(v32)) ) return FALSE;
				if( !testbit( hash_001(v32)) ) return FALSE;
				if( !testbit( hash_004(v32)) ) return FALSE;
				return TRUE;
			}
		protected:
			inline uint32_t hash_001( uint32_t v32 )
			{
				uint32_t _hash = v32;
				return _hash % bits();
			}
			inline uint32_t hash_002( uint32_t v32 )
			{
				uint32_t _hash = (uint32_t)(v32 >> 7);
				return _hash%bits();
			}
			inline uint32_t hash_003( uint32_t v32 )
			{
				uint32_t _hash = v32 * 0xDEADBEEF;
				return _hash%bits();
			}
			inline uint32_t hash_004( uint32_t v32 )
			{
				uint32_t _hash  = v32; _hash *= 711;
				_hash |= v32 >>= 3; _hash *= 1711;
				_hash |= v32 >>= 3; _hash *= 2711;
				_hash |= v32 >>= 3; _hash *= 3711;
				_hash |= v32 >>= 3; 
				return _hash%bits();
			}
		};

		struct filter32_t
		{
			skiptable_t	_shift;
			bloom32_t	_bloom;

			bool_t init( size_t cv32 )
			{
				size_t bits = cv32 * 16;
				if( bits < 0x1000 ) bits = 0x1000;
				return _bloom.resize( bits, true );
			}

			bool_t add( uint32_t * v32p )
			{
				_shift.addu32( v32p );
				_bloom.addu32( v32p );
				return true;
			}

			// return 0 means maybe hit
			size_t test( uint32_t * v32p )
			{
				size_t k = _shift.get_shift( v32p );
				if( k ) return k;
				if( !_bloom.maybe_hit(v32p) )
					return 1;
				return 0;
			}

			void clear()
			{
				_bloom.resize(0);
				_shift.clear();
			}

		};

	};






};


#endif